class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> vis;//用来标记已经搜索过的状态
        unordered_set<string> hash(bank.begin(), bank.end());
        string change = "AGCT";

        if(startGene == endGene) return 0;
        if(!hash.count(endGene)) return -1;

        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        int ret = 0;

        while(q.size())
        {
            ret++;
            int sz = q.size();
            while(sz--)
            {
                string t = q.front();
                q.pop();
                for(int i = 0; i < 8; i++)
                {
                    string tmp = t;
                    for(int j = 0; j < 4; j++)
                    {
                        tmp[i] = change[j];
                        if(hash.count(tmp) && !vis.count(tmp))
                        {
                            if(tmp == endGene) return ret;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};